public class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity){
        this.capacity =capacity;
        this.size = 0;
        this.heap =new int[capacity];
    }
    private int parent(int i){
        return (i-1)/2;
    }

    private  int leftChild(int i){
        return 2*i +1;
    }

    private int rightChild(int i) {
        return 2 * i + 2;
    }

    // 插入元素
    public void insert(int value) {
        if (size >= capacity) {
            throw new IllegalStateException("Heap is full");
        }
        heap[size] = value;
        size++;
        heapifyUp(size - 1);
    }

    // 删除堆顶元素
    public int extractMin() {
        if (size <= 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int min = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return min;
    }

    // 向上调整
    private void heapifyUp(int i) {
        while (i > 0 && heap[parent(i)] > heap[i]) {
            swap(parent(i), i);
            i = parent(i);
        }
    }

    // 向下调整
    private void heapifyDown(int i) {
        int minIndex = i;
        int left = leftChild(i);
        int right = rightChild(i);

        if (left < size && heap[left] < heap[minIndex]) {
            minIndex = left;
        }
        if (right < size && heap[right] < heap[minIndex]) {
            minIndex = right;
        }
        if (i != minIndex) {
            swap(i, minIndex);
            heapifyDown(minIndex);
        }
    }

    // 交换元素
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    // 堆排序
    public void heapSort() {
        for (int i = size / 2 - 1; i >= 0; i--) {
            heapifyDown(i);
        }
        for (int i = size - 1; i > 0; i--) {
            swap(0, i);
            size--;
            heapifyDown(0);
        }
        size = heap.length;
    }
   //堆有点类似于通过数组维护的树
    public static void main(String[] args) {
        MinHeap heap = new MinHeap(10);
        heap.insert(5);
        heap.insert(3);
        heap.insert(8);
        heap.insert(1);
        heap.insert(10);

        System.out.println("Extracted min: " + heap.extractMin());
        heap.heapSort();
        System.out.println("Heap after sorting:");
        for (int i = 0; i < heap.size; i++) {
            System.out.print(heap.heap[i] + " ");
        }
    }

}
